package com.linchong.dynamicprogramming.hard;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-19 13:51
 * @Description: BuySellStockIII$123-买卖股票的最佳时机3-https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 */
public class BuySellStockIII {


	/**
	 *
	 *
	 *
	 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
	 *
	 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
	 *
	 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 *
	 * 示例 1:
	 *
	 * 输入: [3,3,5,0,0,3,1,4]
	 * 输出: 6
	 * 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
	 *      随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
	 * 示例 2:
	 *
	 * 输入: [1,2,3,4,5]
	 * 输出: 4
	 * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
	 *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
	 *      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
	 * 示例 3:
	 *
	 * 输入: [7,6,4,3,1]
	 * 输出: 0
	 * 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
	 *
	 *
	 * 【分析】
	 *  股票买卖1：任意买卖一次最大利润
	 *  股票买卖2：任意买卖多次最大利用
	 *  股票买卖3：最多只能进行两次买卖
	 *  所以需要记录已经买卖了多少次
	 *
	 *  step 1 确定状态
	 *      最后一步：最优策略中，最后一次买卖发生在第j天
	 *          此时枚举最后一次买发生在第几天，但是不知道之前有没有买卖过
	 *          举个例子：第j天价格为100,前面第i天价格为30，利润不能用简单的100-30计算，因为不知道第i天之前
	 *      有没有买卖过，买卖过的话，有没有超过两次
	 *
	 *    解决方案：记录阶段
	 *          不知道有没有买过，就记录下来
	 *    整个过程中可以划分为5个阶段：
	 * |———(第一次买之前)---|(第一次买)---(持有股票)---|(第一次卖)---(第一次卖之后，第二次买之前)---|(第二次买)---(持有股票)---|(第二次卖)---(第二次卖之后)---|
	 *
	 * 买卖股票划分阶段，做成了划分型动态规划。虽然不知道是具体的哪一天买卖的，分析可知：
	 * 1.如果什么都没有干，永远在阶段1（第一次买之前）
	 * 2.如果买卖过一次就结束，在阶段3(持有股票)
	 * 3.如果买卖过两次，在阶段5(第二次卖，结束)
	 * 4.它不可能在阶段2或4，因为要获利，买了股票不卖，获不了利润，认为它默认要清仓，要不开始就不买
	 *
	 *
	 * 在此情况下，只需要知道当前前一天是处于什么阶段，就知道还能不能买，
	 * 例如：
	 *          当前是第10天，如果前一天是阶段5，当前就不能买，因为已经处于第二次卖之后了；
	 *                      如果前一天在阶段3，还能卖一次；
	 *                      如果前一天是在阶段4，今天可以做：
	 *                          继续持有，今天的获利=今天的价格-前一天的价格；
	 *                          今天卖掉，钱拿到手，从阶段4跳到阶段5，不能买卖，可以结束
	 *
	 * 阶段可以保持：即不进行买卖操作。
	 * 阶段可以变化：买或卖
	 *      在阶段2，卖了一股，进入阶段3
	 *      在阶段2，卖了一股，同时当天有买了一股，进入阶段4
	 *              卖了一股，又买了一股，当天又卖了一股：这种情况未获利，白白浪费了一次机会，没有意义，不用考虑。
	 *
	 * 综上：最优策略一定是前N天（第N-1天）结束后，处于：
	 *      阶段1：没买卖过
	 *      阶段3：买卖过1次
	 *      阶段5：买卖过2次
	 *
	 * 例如，如果要求前N天(第N-1天)结束后，在阶段5的获利，设f[N][5]
	 *      情况1：第N-2天就在阶段5--f[N-1][5]
	 *      情况2：第N-2天还在阶段4(第二次持有股票)，第N-1天卖掉--f[N-1][4]+(P(N-1)-P(N-2))
	 *
	 * 例如，如果要求前N天(第N-1天)结束后,在阶段4的获利，设f[N][4]
	 *      情况1：第N-2天就在阶段4--f[N-1][4]+(P(N-1)-P(N-2))
	 *      情况2：第N-2天在阶段3--f[N-1][3]
	 *      情况3：第N-2天在阶段2,第N-1天卖了有立即买入--f[N-2][2]+(P(N-1)-P(N-2))
	 *
	 *   子问题：要求f[N][1],...,f[N][5],需要知道f[N-1][1],...,f[N-1][5]
	 *   状态：f[i][j]表示前i天(第i-1天)结束后，在阶段j的最大获利。
	 *
	 * step 2:转移方程
	 *      f[i][j]表示前i天(第i-1天)结束后，在阶段j的最大获利
	 *          阶段1,3,5 ---手中无股票状态
	 *              f[i][j] = max{f[i-1][j],f[i-1][j]+(P（i-1）-P（i-2）)}
	 *                          昨天没有持有股票        昨天持有，今天清仓
	 *          阶段2,4  ---手中持有股票状态
	 *              f[i][j] = max{f[i-1][j]+(P（i-1）-P（i-2）),f[i-1][j-1],f[i-1][j-2]+(P（i-1）-P（i-2）)}
	 *                      昨天持有，今天持有并获利    昨天没有持有，今天刚买入        昨天持有上一次股票，今天卖出并立即买入
	 *
	 * step 3:初始条件和边界情况：
	 *      刚开始（前0天）处于阶段1
	 *      * f[0][1] = 0
	 *      * f[0][2]=f[0][3]=f[0][4]=f[0][5]=负无穷
	 *
	 *      阶段1,3,5：f[i][j] = max{f[i-1][j],f[i-1][j]+(P（i-1）-P（i-2）)}
	 *
	 *      阶段2,4：f[i][j] = max{f[i-1][j]+(P（i-1）-P（i-2）),f[i-1][j-1],f[i-1][j-2]+(P（i-1）-P（i-2）)}
	 *
	 *      如果j-1<1或j-2<1或i-2<0,对应项不计入max,即下标负数没有意义
	 *
	 *      因为最多买卖两次，所以答案是Max{f[N][1],f[N][3],f[N][5]},即清仓状态下最后一天的最大获利
	 *
	 * step 4:计算顺序
	 *      初始化f[0][1],...,f[0][5]
	 *      f[1][1],...,f[1][5]
	 *      ...
	 *      f[N][1],...,f[N][5]
	 *      时间复杂度：O(N),空间复杂度：O(N),优化后可以O(1),因为f[i][1...5]只依赖于f[i-1][1...5]
	 * 
	 */

	public int maxProfit(int[] prices) {

		int n = prices.length;
		if(n == 0){
			return 0;
		}

		int[][] f = new int[n+1][5+1];

		//init
		// 初始化前0天第一阶段最大获利是0
		f[0][1] = 0;
		f[0][2]=f[0][3]=f[0][4]=f[0][5] = Integer.MIN_VALUE;

		for (int i = 1; i <= n ; i++) {
			// 1,3,5
			for (int j = 1; j <=5 ; j+=2) {
				// f[i][j] = max{f[i-1][j],f[i-1][j]+(P（i-1）-P（i-2）)}
				f[i][j] = f[i-1][j];
				// 负无穷+负数=正数
				if(j>1 && i>1&&f[i-1][j-1]!=Integer.MIN_VALUE){
					f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
				}

			}

			for (int j = 2; j <= 5; j+=2) {
				//max{f[i-1][j]+(P（i-1）-P（i-2）),f[i-1][j-1],f[i-1][j-2]+(P（i-1）-P（i-2）)}
				f[i][j] = f[i-1][j-1];
				if(i>1 && f[i-1][j]!=Integer.MIN_VALUE){
					f[i][j] = Math.max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]);
				}

				if(j>2 && i>1 &&f[i-1][j-2]!=Integer.MIN_VALUE){
					f[i][j] = Math.max(f[i][j],f[i-1][j-2]+prices[i-1]-prices[i-2]);
				}

			}
		}


		return Math.max(Math.max(f[n][1],f[n][3]),f[n][5]);
	}
	public static void main(String[] args) {

		int[] prices = {1,2,4,2,5,7,2,4,9,0};
		BuySellStockIII instance = new BuySellStockIII();
		System.out.println(instance.maxProfit(prices));

	}
}
